Пећине са тунелима
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,1 s | 64 Mb | стандардни излаз | стандардни улаз |
Спелеолози се налазе у улазној дворани пећине, на висини тла, чија је надморска висина позната. Пећина има укупно \(n\) дворана обележених бројевима од \(0\) до \(n-1\) (улазна дворана је обележена бројем \(0\)) и до сваке од њих се може стићи коришћењем неког од многих тунела који их повезују. Сви тунели су двосмерни. Ако се за сваки тунел зна које две дворане повезује и колика је висинска разлика између њих, написати програм који одређује најнижу надморску висину на коју се спелеолози у пећини могу спустити.
Улаз
Са стандардног улаза се учитава висина тла (цео број), а затим, из следеће линије природни број \(n\) (\(1 \leq n \leq 100\)) који представља број дворана и затим природни број \(m\) (\(1\leq m \leq n\cdot(n-1)/2\)) који представља број тунела. У наредних \(m\) линија налазе се по три цела броја раздвојена размацима, која описују тунел: редни број полазне дворане, редни број долазне дворане и висинску разлику имеђу полазне и долазне дворане (негативан број значи да је долазна дворана на мањој надморској висини).
Излаз
На стандардни излаз исписати цео број који представља најнижу надморску висину на којој се налази нека дворана.
Пример
Улаз
696 5 7 0 1 -7 0 4 4 0 3 -6 1 2 -10 1 3 1 1 4 11 3 4 10
Излаз
679
Морате бити улоговани како бисте послали задатак на евалуацију.